package zhoujian.oj.leetcode;

import java.util.Hashtable;

/**
 * Implement strStr().
 * 
 * Returns a pointer to the first occurrence of needle in haystack, 
 * or null if needle is not part of haystack.
 */
public class StrStr {
	
	public String strStr(String haystack, String needle) {
		return bm(haystack, needle);
	}
	
	public String bm(String haystack, String needle) {
		char[] cHaystack = haystack.toCharArray();
		char[] cNeedle = needle.toCharArray();
		int hLength = cHaystack.length;
		int nLength = cNeedle.length;
		
		if (hLength < nLength) {
			return null;
		} else if (haystack.equals(needle)) {
			return haystack;
		} else if (nLength == 0){
			return haystack;
		}

		// last occurrence
		Hashtable<Character, Integer> bmLc = new Hashtable<Character, Integer>();
		for (int i = 0; i < nLength; i++) {
			bmLc.put(cNeedle[i], i);
		}
		
//		for (Entry<Character, Integer> temp : bmLc.entrySet()) {
//			System.out.println(temp.getKey() + ":" + temp.getValue());
//		}
		
		// suffix
		int[] suffix = new int[nLength];
		suffix[nLength - 1] = nLength;
		for (int i = nLength - 2; i >= 0; i--) {
			int j = i;
			while (j >= 0 && cNeedle[j] == cNeedle[nLength - 1 - i + j]) {
				j--;
			}
			suffix[i] = i - j; 
		}
		
//		for (int i = 0; i < nLength; i++) {
//			System.out.println(suffix[i]);
//		}
		
		// good suffix
		int[] bmGs = new int[nLength];
		bmGs[nLength - 1] = 1;
		for (int i = nLength - 2; i >= 0; i--) {
			int bcSfx = nLength - 1 - i;
			int j = nLength - 1;
			while (j > bcSfx - 1  && suffix[j] != bcSfx) {
				j--;
			}
			if (suffix[j] == bcSfx) {
				bmGs[i] = nLength - 1 - j;
			} else {
				int t = 0;
				for (int k = 0; k < bcSfx; k++) {
					if (suffix[k] > t) {
						t = suffix[k];
					}
				}
				bmGs[i] = nLength - t;
			}
		}
		
//		for (int i = 0; i < nLength; i++) {
//			System.out.println(bmGs[i]);
//		}	

		int j = 0;
		while (j <= hLength - nLength) {
			int i = nLength - 1;
			for (; i >= 0 && cNeedle[i] == cHaystack[i + j]; i--);
			if (i < 0) {
				return haystack.substring(j);
			} else {
//				System.out.print("i=" +i+ "|");
//				System.out.print(cHaystack[i + j] + "|");
//				System.out.print(bmLc.get(cHaystack[i + j]) + "|");
//				System.out.print(bmGs[i] + "|");
//				System.out.println(i - (bmLc.get(cHaystack[i + j]) == null ? -1 : bmLc.get(cHaystack[i + j])));
				j += Math.max(bmGs[i], i - (bmLc.get(cHaystack[i + j]) == null ? -1 : bmLc.get(cHaystack[i + j])));
			}
		}
		
		return null;
	}
	
	public String kmp2(String haystack, String needle) {
		char[] cHaystack = haystack.toCharArray();
		char[] cNeedle = needle.toCharArray();
		int hLength = cHaystack.length;
		int nLength = cNeedle.length;
		
		if (hLength < nLength) {
			return null;
		} else if (haystack.equals(needle)) {
			return haystack;
		} else if (nLength == 0){
			return haystack;
		}
		
		int[] jump = new int[nLength];
		jump[0] = -1;
		for (int i = 1; i < nLength; i++) {
			int cmpPos = jump[i - 1];
			while (cmpPos >= 0 && cNeedle[cmpPos] != cNeedle[i - 1]) {
				cmpPos = jump[cmpPos];
			}
			
			if (cmpPos >= 0 && cNeedle[cmpPos] == cNeedle[i - 1]) {
				jump[i] = jump[i - 1] + 1;
			} else {
				jump[i] = 0;
			}
		}
		
		int i = 0;
		int j = 0;
		while (i < hLength && j < nLength) {
			if (cHaystack[i] == cNeedle[j]) {
				i++;
				j++;
			} else {
				j = jump[j];
				if (j == -1) {
					j++;
					i++;
				}
			}
		}
		
		if (j == nLength) {
			return haystack.substring(i - j);
		} else {
			return null;
		}
	}
	
	public String kmp1(String haystack, String needle) {
        char[] cHaystack = haystack.toCharArray();
        char[] cNeedle = needle.toCharArray();
        int hLength = cHaystack.length;
        int nLength = cNeedle.length;
        
        if (hLength < nLength) {
        	return null;
        } else if (haystack.equals(needle)) {
        	return haystack;
        } else if (nLength == 0){
        	return haystack;
        }
        
        int index;
        int[] overlayValue = new int[nLength];
        overlayValue[0] = 0;
        
        for (int i = 1; i < nLength; i++) {
        	index = overlayValue[i - 1];
        	
        	while (index > 0 && cNeedle[index] != cNeedle[i]) {
        		index = overlayValue[index - 1];
        	}
        	
        	if (cNeedle[index] == cNeedle[i]) {
        		overlayValue[i] = index + 1;
        	} else {
        		overlayValue[i] = 0;
        	}
        }
        
        int hIndex = 0;
        int nIndex = 0;
        while (hIndex < hLength && nIndex < nLength) {
        	if (cHaystack[hIndex] == cNeedle[nIndex]) {
        		hIndex++;
        		nIndex++;
        	} else if (nIndex == 0) {
        		hIndex++;
        	} else {
        		nIndex = overlayValue[nIndex - 1];
        	}
        }
        
        if (nIndex == nLength) {
        	return haystack.substring(hIndex - nIndex);
        } else {
        	return null;
        }
        
    }

	public static void main(String[] args) {
		String source;
		String pattern;
		
		source = "HERE IS A SIMPLE EXAMPLE";
		pattern = "EXAMPLE";
		System.out.println((new StrStr()).strStr(source, pattern));
		
		source = "ABC ABCDAB ABCDABCDABDE";
		pattern = "ABCDABD";
		System.out.println((new StrStr()).strStr(source, pattern));
		
		source = "annbcdanacadsannannacanna";
		pattern = "annacanna";
		System.out.println((new StrStr()).strStr(source, pattern));
		
		source = "";
		pattern = "";
		System.out.println((new StrStr()).strStr(source, pattern));
		
		source = "bbaa";
		pattern = "aab";
		System.out.println((new StrStr()).strStr(source, pattern));
		
		source = "a";
		pattern = "a";
		System.out.println((new StrStr()).strStr(source, pattern));
	}

}
